import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author hewei
 * @version 1.0
 * @description: 1081. 不同字符的最小子序列
 * @date 2022/11/15 15:17
 */

public class SmallestSubsequence {

    public String smallestSubsequence(String s) {
        char[] chars = s.toCharArray();
        int[] count = new int[26];
        for (char c : chars) {
            count[c - 'a']++;
        }
        boolean[] flag = new boolean[26];
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : chars) {
            --count[c - 'a'];
            if (flag[c - 'a']) continue;
            while (!stack.isEmpty() && c < stack.peekFirst() && count[stack.peekFirst() - 'a'] > 0) {
                Character pollFirst = stack.pollFirst();
                flag[pollFirst - 'a'] = false;
            }
            stack.offerFirst(c);
            flag[c - 'a'] = true;
        }
        StringBuilder stringBuilder = new StringBuilder();
        while (!stack.isEmpty()) {
            stringBuilder.append(stack.pollLast());
        }
        return stringBuilder.toString();
    }
}
